/*
 * @lc app=leetcode.cn id=918 lang=cpp
 * @lcpr version=30204
 *
 * [918] 环形子数组的最大和
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        // 从数组开头（下标 0）到当前下标 i 的所有「前缀和」中的最大值
        vector<int> leftMax(n); 
        // 对坐标为 0 处的元素单独处理，避免考虑子数组为空的情况
        leftMax[0] = nums[0];   // 第一个元素的前缀最大值就是自身
        int leftSum = nums[0];  // 初始前缀和为第一个元素
        int pre = nums[0];      // 初始以第一个元素结尾的子数组和为自身
        int res = nums[0];      // 初始最大和为第一个元素
        for (int i = 1; i < n; i++) {
            // 计算以当前元素结尾的子数组的最大和（普通子数组情况）
            pre = max(pre + nums[i], nums[i]);
            // 更新全局最大和
            res = max(res, pre);
            // 累计前缀和
            leftSum += nums[i];
            // 更新前缀最大值数组（取之前的最大值和当前前缀和的较大者）
            leftMax[i] = max(leftMax[i - 1], leftSum);
        }

        // 从右到左枚举后缀，固定后缀，选择最大前缀
        int rightSum = 0;
        for (int i = n - 1; i > 0; i--) {
            // 累计后缀和（从数组末尾向头部累加）
            rightSum += nums[i];
            // 计算环形子数组的最大和：当前后缀和 + 左侧最大前缀和（不包含当前元素）
            res = max(res, rightSum + leftMax[i - 1]);
        }
        return res;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [1,-2,3,-2]\n
// @lcpr case=end

// @lcpr case=start
// [5,-3,5]\n
// @lcpr case=end

// @lcpr case=start
// [3,-2,2,-3]\n
// @lcpr case=end

 */

